Random Walk in a N-cube Without Hamiltonian Cycle to Chaotic Pseudorandom Number Generation: Theoretical and Practical Considerations

摘要

Designing a pseudorandom number generator (PRNG) is a difficult and complextask. Many recent works have considered chaotic functions as the basis of builtPRNGs: the quality of the output would indeed be an obvious consequence of somechaos properties. However, there is no direct reasoning that goes from chaoticfunctions to uniform distribution of the output. Moreover, embedding such kindof functions into a PRNG does not necessarily allow to get a chaotic output,which could be required for simulating some chaotic behaviors. In a previous work, some of the authors have proposed the idea of walkinginto a $\mathsf{N}$-cube where a balanced Hamiltonian cycle has been removed asthe basis of a chaotic PRNG. In this article, all the difficult issues observedin the previous work have been tackled. The chaotic behavior of the whole PRNGis proven. The construction of the balanced Hamiltonian cycle is theoreticallyand practically solved. An upper bound of the expected length of the walk toobtain a uniform distribution is calculated. Finally practical experiments showthat the generators successfully pass the classical statistical tests.